package own.stu.jobgib.playown.alg.solution.dp;

/**
 * 双序列dp
 * <li />顾名思义，有两人序列/字符串，需要进行一些操作
 * <li />每人序列本身是一维的
 * <li />可以转化为二维动态规划
 * <p>
 * <li/>总结
 * <li/>两个一维序列/字符串
 * <li/>突破口
 * <li/>- 串A和串B的最后一个字符是否匹配
 * <li/>- 是否需要串A/串B的最后一人字符
 * <li/>- 缩减问题规模
 * <li/>数组下标表示序列A前i个，序列B前j个: f[i][j]
 * <li/>初始条件和边界情况究串如何处理
 * <li/>- 空串如何处理
 * <li/>- 计数型(情况1+情况2+...)以及最值型(min/max[情况1，情况2，...J)
 * <li/>匹配的情况下勿忘+1(操作数多1次，匹配长度多1)
 */
public class DoubleSequenceType {

    public static void main(String[] args) {
        DoubleSequenceType d = new DoubleSequenceType();
        // System.out.println(d.longestCommonSubsequence("abcde", "ace"));

        // System.out.println(d.isInterleave("aabcc", "dbbca", "aadbbcbcac"));

        // System.out.println(d.minDistance("horse", "ros"));
        // System.out.println(d.minDistance("intention", "execution"));

        // System.out.println(d.numDistinct("rabbbit", "rabbit"));
        // System.out.println(d.numDistinct("babgbag", "bag"));

        // System.out.println(d.isMatch("aa", "a"));
        // System.out.println(d.isMatch("aa", "a*"));
        // System.out.println(d.isMatch("aa", ".*"));
        // System.out.println(d.isMatch("aab", ".*"));

        // System.out.println(d.isWildMatch("aa", "a"));
        // System.out.println(d.isWildMatch("aa", "*"));
        // System.out.println(d.isWildMatch("ab", "?a"));
        // System.out.println(d.isWildMatch("aab", "c*a*b"));
        // System.out.println(d.isWildMatch("adceb", "*a*b"));

        System.out.println(d.findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 5, 3));
    }

    /**
     * 1143. 最长公共子序列
     * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
     * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     * <p>
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
     * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
     * <p>
     * 示例：
     * 输入：text1 = "abcde", text2 = "ace"
     * 输出：3
     * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
     */
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
            return 0;
        }
        int n = text1.length(), m = text2.length();
        /*
        dp[i][j]表示子串 s1.（0..i) 和s2.(0...j)的最长公共子序列
        dp[i][j]
        max(dp[i - 1][j], dp[i][j-1])
        max(dp[i-1][j-1](s.(i) == s.(j))
        初始值
        dp[0][0] = 0; 空串的初始值为0
         */
        int[][] dp = new int[n + 1][m + 1];
        int[][] pi = new int[n + 1][m + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (dp[i][j] == dp[i - 1][j]) {
                    pi[i][j] = 0;
                } else {
                    pi[i][j] = 1;
                }
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
                    if (dp[i][j] == dp[i - 1][j - 1] + 1) {
                        pi[i][j] = 2;
                    }
                }
            }
        }

        int len = dp[n][m];// 最长公共子窜长度
        char[] res = new char[len];
        int idx = len - 1;
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (pi[i][j] == 0) {
                --i;
            } else if (pi[i][j] == 1) {
                --j;
            } else {
                res[idx--] = text1.charAt(i - 1);
                --i;
                --j;
            }
        }

        System.out.println("lcs: ");
        for (char re : res) {
            System.out.print(re + ", ");
        }
        System.out.println();

        return dp[n][m];
    }

    /**
     * 97. 交错字符串
     * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
     * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
     * s = s1 + s2 + ... + sn
     * t = t1 + t2 + ... + tm
     * |n - m| <= 1
     * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
     * 注意：a + b 意味着字符串 a 和 b 连接。
     * <p>
     * 示例：
     * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
     * 输出：true
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        int n = s1.length(), m = s2.length(), p = s3.length();
        if (n + m != p) return false;
        /*
        dp[i][j][k] = 表示 前 s1.(i)子串 和 前 s2.(j)子串 能否 组成 前s3.(k)子串
        s1(i) != s3(k) && s2(j)!=s3(k) return fasle;
        s1(i) == s3(k) dp[i - 1][j][k - 1]
        s2(j) == s3(k) dp[i][j - 1][k - 1]

        dp[0][0][0] = true;

        可以简化为二维 因为 i + j = k
         */
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] |= dp[i - 1][j];
                }
                if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
                    dp[i][j] |= dp[i][j - 1];
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 72. 编辑距离
     * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
     * 你可以对一个单词进行如下三种操作：
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     * <p>
     * 示例：
     * 输入：word1 = "horse", word2 = "ros"
     * 输出：3
     * 解释：
     * horse -> rorse (将 'h' 替换为 'r')
     * rorse -> rose (删除 'r')
     * rose -> ros (删除 'e')
     */
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }
        int n = word1.length();
        int m = word2.length();
        if (n == 0) return m;
        /*
        dp[i][j]表示将前w1.(i)个字符 转换为前w2.(j)个字符的最少操作数
        dp[i - 1][j - 1] (s[i] == t[j])
        dp[i - 1][j - 1] + 1 替换一个字符
        dp[i - 1][j] + 1（s 删除一个字符）
        dp[i][j - 1] + 1（s 插入一个字符）

        初始值：空串和长度为l的编辑距离为l
         */
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i; // w2 为空串
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = i; // w1为空串
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                if (c1 == c2) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 115. 不同的子序列
     * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
     * <p>
     * 示例：
     * 输入：s = "rabbbit", t = "rabbit"
     * 输出：3
     * 解释：
     * 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
     * rabbbit
     * rabbbit
     * rabbbit
     */
    public int numDistinct(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }
        /*
        dp[i][j] 表示t的前j个字符在s的前i个字符中出现的次数
        dp[i - 1][j] t[j] != s[i] ，dp[i][j]就是t的前j个字符在s的前i-1个字符中出现的次数
        dp[i - 1][j - 1] t[j] == s[i] ,dp[i][j]就是t的前j - 1个字符在s的前i-1个字符中出现的次数

        初始值
        dp[i][0] = 1， t为空串，那么在s中出现的次数为1
        dp[0][j] = 0, s为空串，那么t在s中出现的次数为0 // 这里代码可以不处理，默认值
         */
        int n = s.length(), m = t.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 10. 正则表达式匹配
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
     * <p>
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
     * <p>
     * 示例：
     * 输入：s = "aa", p = "a"
     * 输出：false
     * 解释："a" 无法匹配 "aa" 整个字符串。
     */
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int n = s.length(), m = p.length();
        /*
        dp[i][j]表示s的前i个字符是否匹配p的前j个字符
        如果p[j] 不等于 '.' 或者'*' 那么 dp[i][j] = dp[i - 1][j - 1]
        如果p[j] = '.' dp[i][j] = dp[i - 1][j - 1] 不管s[i]是哪个字符，'.'都能匹配一个
        如果p[j] = '*' ，那么代表p[j-1]能够有0-多个，如果
        s[i] != p[j-1] 则dp[i][j] = dp[i - 1][j - 2]
        s[i] == p[j-1] 或者 p[j-1] = '.' 则 dp[i][j] = dp[i-1][j]

        初始化
        dp[i][0] = false;
        dp[0][0] = true; 空串能够匹配空串
         */
        boolean[][] dp = new boolean[n + 1][m + 1];
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) { // 这里注意s串要从0开始，因为可能匹配'.*'
            for (int j = 1; j <= m; j++) {
                char c2 = cp[j - 1];
                if (c2 != '*') {
                    if (i > 0 && (cs[i - 1] == c2 || c2 == '.')) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    if (j > 1) { //* 必须和字母或者'.'匹配，因此j>1
                        dp[i][j] |= dp[i][j - 2];

                        if (i > 0) {
                            char c1 = cs[i - 1];
                            char c3 = cp[j - 2];
                            if (c3 == c1 || c3 == '.') {
                                dp[i][j] |= dp[i - 1][j];
                            }
                        }
                    }
                }
            }
        }

        return dp[n][m];
    }

    /**
     * 44. 通配符匹配
     * 给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
     * '?' 可以匹配任何单个字符。
     * '*' 可以匹配任意字符序列（包括空字符序列）。
     * 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
     * <p>
     * 示例：
     * 输入：s = "aa", p = "a"
     * 输出：false
     * 解释："a" 无法匹配 "aa" 整个字符串。
     */
    public boolean isWildMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int n = s.length(), m = p.length();
        /*
        dp[i][j]
        s[i] == p[i] || p[i] == '?' dp[i][j] = dp[i - 1][j - 1]
        p[i] == '*'
        dp[i][j] = dp[i - 1][j]      s[i]能够与'*'匹配
        dp[i][j] = dp[i - 1][j - 1]  s[i]不能够与'*'匹配

        初始值
        dp[i][0] = false;
        dp[0][0] = true;
         */
        boolean[][] dp = new boolean[n + 1][m + 1];
        /*
        可以不写，默认值
        for(int i = 0; i <= n; i ++){
            dp[i][0] =false;
        }*/
        dp[0][0] = true;
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c2 = cp[j - 1];
                if (c2 == '*') {
                    // 这里重点
                    dp[i][j] = dp[i][j - 1];
                    if (i > 0) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    }
                } else {
                    if (i > 0) {
                        char c1 = cs[i - 1];
                        if (c1 == c2 || c2 == '?') {
                            dp[i][j] |= dp[i - 1][j - 1];
                        }
                    }
                }
            }
        }

        return dp[n][m];
    }

    /**
     * 474. 一和零
     * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
     * 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
     * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
     * <p>
     * 示例：
     * 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
     * 输出：4
     * 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
     * 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
     */
    public int findMaxForm(String[] strs, int m, int n) {
        // write your code here
        if (strs == null || strs.length == 0 || m < 0 || n < 0) {
            return 0;
        }

        int[][] nums = new int[strs.length][2];
        for (int l = 0; l < strs.length; l++) {
            String s = strs[l];
            int i = 0, j = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') {
                    i++;
                } else {
                    j++;
                }
            }
            nums[l] = new int[]{i, j};
        }

        /*
        dp[i][j][k] 表示前i个0，前j个1,能够组成前k个子串（这个思路不对，因为k可以跳着挑，如果第一个子串不行，第二个子串可以，不方便处理）
        ----
        dp[k][i][j] 表示前k个子串，最多能有多少个能被前i个0，前j个1组成
        dp[k - 1][i - a(0)][j - b(1)] + 1 (用到了s[k]字符串）
        dp[k - 1][i][j]  (未用到了s[k]字符串）

        初始值
        dp[0][i][j] = 0;// 0个子串，最多就是0个
         */
        int K = strs.length;
        int[][][] dp = new int[K + 1][m + 1][n + 1];
        for (int k = 1; k <= K; k++) {
            int[] num = nums[k - 1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    dp[k][i][j] = dp[k -  1][i][j];
                    if (i >= num[0] && j >= num[1]) {
                        dp[k][i][j] = Math.max(dp[k][i][j], dp[k - 1][i - num[0]][j - num[1]] + 1);
                    }
                }
            }
        }
        return dp[K][m][n];
    }
}